home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / Clean 1.2.4 / Small Demos / invperm.icl < prev    next >
Encoding:
Text File  |  1995-03-13  |  1.8 KB  |  66 lines  |  [TEXT/3PRM]
  1. module invperm
  2.  
  3. /*
  4. Inverse Permutation.
  5.  
  6. Inverts the permutation represented by the list InitPerm.
  7. When a permutation of the form (n,n-1,...,2,1) is inverted this
  8. algorithm runs in linear time. The average (and worst) case
  9. behavior is however quadratic (in the size of the permutation).
  10.  
  11. Run the program with the Show Constructors option on (Application options)
  12. */
  13.  
  14. import StdInt, StdMisc
  15.  
  16. /*    A permutation (Perm) is represented as a list of integers.
  17.     The resulting inverse permutation (TPerm) is built up as a list of
  18.     tuples (TElt) containing an elements and its index, sorted on index.
  19. */
  20. ::Perm        :== [Int]
  21. ::Index_new    :== Int
  22. ::TElt        :== (Index_new,Int)
  23. ::TPerm        :== [TElt]
  24.  
  25. //    The initial permutation.
  26. //    inverse: [10,12,17,7,1,11,19,18,3,8,4,6,5,14,15,16,2,9,13].
  27.  
  28. InitPerm::Perm
  29. InitPerm = [5,17,9,11,13,12,4,10,18,1,6,2,19,14,15,16,3,8,7]
  30.  
  31. //    InvPerm returns the inverse of the permutation p by means of calling Ip.
  32.  
  33. InvPerm::Perm -> Perm
  34. InvPerm p =  Ip 1 [] p
  35.  
  36. /*    Ip inverts a permutation (3rd arg) by using the i'th element of
  37.     the initial permutation as index for i, which becomes the element
  38.     of the inverse permutation ('imperative': ip[p[i]] := i). At the
  39.     end the indices have to be removed from the inverse by means of 
  40.     the function Strip.
  41. */
  42. Ip::Index_new TPerm Perm -> Perm
  43. Ip i ip []        =  Strip ip
  44. Ip i ip [e:pr]    =  Ip (i + 1) (Update_new ip e i) pr
  45.  
  46.  
  47. /*    Update adds an element to a list of (index,value)-pairs (a TPerm)
  48.     that is sorted on index.
  49. */
  50. Update_new::TPerm Index_new Int -> TPerm
  51. Update_new []               i x            =  [(i,x)]
  52. Update_new [e=:(j,y) : ar] i x    | i<j    =  [(i,x), e : ar]
  53.                                         =  [e : Update_new ar i x]
  54.  
  55. //    Strip removes the (superfluous) indices from the resulting permutation.
  56.  
  57. Strip::TPerm -> Perm
  58. Strip []             =  []
  59. Strip [(i,x):ar]    =  [x : Strip ar]
  60.  
  61.  
  62. //    The Start rule: invert the initial permutation.
  63.  
  64. Start::Perm
  65. Start = InvPerm InitPerm
  66.